package tree;

import complexity.Queue;

public class BinaryTree<Key extends Comparable<Key>,V>  {
    private Node root;
    private int N;
    public BinaryTree(){
        this.root = null;
        this.N=0;
    }
    public int size(){
        return this.N;
    }
    public void put(Key key,V value){
       this.root= put(root,key,value);
    }
    private Node put(Node node, Key key,V value){
        if (node==null){
            this.N++;
            return new Node(key,value,null,null);
        }
        int better = key.compareTo(node.key);
        if (better>0){
            node.right = put(node.right, key, value);
        }else if (better<0){
            node.left = put(node.left, key, value);
        }else {
            node.value=value;
        }
        return node;
    }
    public V get(Key key){
        return  get(root,key);
    }

    private V get(Node node, Key key) {
        if (node==null) {
            return null;
        }
        int compare = key.compareTo(node.key);
        if (compare > 0) {
            return get(node.right, key);
        } else if (compare < 0) {
            return get(node.left, key);
        } else {
            return node.value;
        }
    }
    public void delete(Key key){
        delete(root,key);
    }

    private Node delete(Node node, Key key) {
        if (node==null){
            return null;
        }
        int compare = key.compareTo(node.key);
        if (compare>0){
            node.right =delete(node.right,key);
        }else if (compare<0){
            node.left=delete(node.left,key);
        }else {
            this.N--;
            System.out.println("删除的元素是 "+node.value);
            if (node.right==null){
                return node.left;
            }
            if (node.left==null){
                return node.right;
            }
            //删除右子树中最小的节点
            Node newNode = node.right;
            while (newNode.left!=null){
                newNode = newNode.left;
            }
            Node n = node.right;
            //删除最后一个左子节点
            while (n.left!=null){
                if (n.left.left==null){
                    n.left=null;
                }else {
                    n=n.left;
                }
            }
            //让node节点的左子树成为newNode的左子树
            newNode.left = node.left;
            //让node节点的右子树成为newNode的右子树
            newNode.right = node.right;
            node = newNode;
        }
        return node;
    }
    public Key minNode(){
        return minNode(root).key;
    }
    private Node minNode(Node node){
        if (node.left!=null){
            return minNode(node.left);
        }else {
            return node;
        }
    }
    public Key maxNode(){
        return maxNode(root).key;
    }
    private Node maxNode(Node node) {
        if (node.right!=null){
            return maxNode(node.right);
        }else {
            return node;
        }
    }

    /**
     * 先序遍历实现方法如下
     * @return 队列
     */
    public Queue<Key> preErgodic(){
        Queue<Key> queue = new Queue<>();
        preErgodic(root, queue);
        return queue;
    }

    /**
     * 获取指定node的key存放到queue中
     * @param node
     * @param queue
     */
    private void preErgodic(Node node, Queue<Key> queue){
        if (node==null){
            return;
        }
        queue.enqueue(node.key);
        //递归调用方法获取左子树
        if (node.left!=null){
            preErgodic(node.left,queue);
        }
//        queue.enqueue(root.key);
        //递归调用方法获取右子树
        if (node.right!=null){
            preErgodic(node.right,queue);
        }
    }

    /**
     * 中序遍历实现代码
     */
    public Queue<Key> midErgodic(){
        Queue<Key> queue = new Queue<>();
        midErgodic(this.root,queue);
        return queue;
    }

    private void midErgodic(Node node, Queue<Key> queue) {
        if (node==null){
            return;
        }
        if (node.left!=null){
            midErgodic(node.left,queue);
        }
        queue.enqueue(node.key);
        if (node.right!=null){
            midErgodic(node.right,queue);
        }
    }
    public Queue<Key> lastErgodic(){
        Queue<Key> queue = new Queue<>();
        lastErgodic(this.root,queue);
        return queue;
    }

    private void lastErgodic(Node node, Queue<Key> queue) {
        if (node==null){
            return;
        }
        if (node.left!=null){
            lastErgodic(node.left,queue);
        }
        if (node.right!=null){
            lastErgodic(node.right,queue);
        }
        queue.enqueue(node.key);
    }
    public Queue<Key> layerErgodic(){
        Queue<Key> queue = new Queue<>();
        Queue<Node> nodeQueue = new Queue<>();
        if (this.root==null){
            return null;
        }
        nodeQueue.enqueue(this.root);
        while (!nodeQueue.isEmpty()){
            //从队列中出队一个节点 将key存放在队列中
            Node node = nodeQueue.dequeue();
            queue.enqueue(node.key);
            //判断有没有左子节点放入到队列中
            if (node.left!=null){
                nodeQueue.enqueue(node.left);
            }
            //判断有没有右子节点放入到队列中
            if (node.right!=null){
                nodeQueue.enqueue(node.right);
            }
        }
        return queue;
    }
    //求二叉树的最大深度问题
    //获取整个树的最大深度
    public int maxDepth(){
        return maxDepth(this.root);
    }
    //获取指定树x的最大深度
    private int maxDepth(Node node){
        if (node==null){
            return 0;
        }
        int left = 0;
        int right = 0;
        //计算左子树的最大深度
        if (node.left!=null){
           left= maxDepth(node.left);
        }
        if (node.right!=null){
           right= maxDepth(node.right);
        }
        //计算右子树的最大深度
        int high = left > right ? left +1: right +1;
        return high;
        //比较左子树最大深度 和 左子树最大深度 取最大值+1返回最大深度
    }
    private class Node{
        private Key key;
        private V value;
        private Node left;
        private Node right;
        public Node(Key key, V value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
